package com.example.practice.class04;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

/**
 * @Date 2022/9/12
 * @Author Jonathan
 * @Description 大楼轮廓线问题
 * @link {https://leetcode.com/problems/the-skyline-problem/}
 * todo  再思考思考！！！
 */
public class Code08_TheSkylineProblem {
    public static void main(String[] args) {
        int[][] buildings = new int[][]{{2, 9, 10}, {3, 7, 15}, {5, 12, 12}, {15, 20, 10}, {19, 24, 8}};
        System.out.println(getSkyline(buildings));
    }


    public static List<List<Integer>> getSkyline(int[][] buildings) {
        Node[] nodes = new Node[buildings.length * 2];
        for (int i = 0; i < buildings.length; i++) {
            nodes[i * 2] = new Node(buildings[i][0], true, buildings[i][2]);
            nodes[i * 2 + 1] = new Node(buildings[i][0], false, buildings[i][2]);
        }
        // 根据x轴排序
        Arrays.sort(nodes, new NodeComparator());
        // 两个map
        TreeMap<Integer, Integer> mapHeightTimes = new TreeMap<>();
        TreeMap<Integer, Integer> mapXHeight = new TreeMap<>();
        for (Node node : nodes) {
            // 加
            if (node.isAdd) {
                if (!mapHeightTimes.containsKey(node.h)) {
                    // 没有就放进去 且计数为1
                    mapHeightTimes.put(node.h, 1);
                } else {
                    // 有就  原来计数加一
                    mapHeightTimes.put(node.h, mapHeightTimes.get(node.h) + 1);
                }
            } else {
                if (mapHeightTimes.get(node.h) == 1) {
                    mapHeightTimes.remove((node.h));
                } else {
                    mapHeightTimes.put(node.h, mapHeightTimes.get(node.h) - 1);
                }
            }

            if (mapHeightTimes.isEmpty()) {
                mapXHeight.put(node.x, 0);
            } else {
                mapXHeight.put(node.x, mapHeightTimes.lastKey());
            }
        }

        List<List<Integer>> ans = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : mapXHeight.entrySet()) {
            final Integer curX = entry.getKey();
            final Integer curMaxHeight = entry.getValue();
            if (ans.isEmpty() || ans.get(ans.size() - 1).get(1) != (curMaxHeight)) {
                ans.add(new ArrayList<>(Arrays.asList(curX, curMaxHeight)));
            }
        }
        return ans;
    }


    public static class Node {
        public int x;
        public boolean isAdd;
        public int h;

        public Node(int x, boolean isAdd, int h) {
            this.x = x;
            this.isAdd = isAdd;
            this.h = h;
        }
    }

    public static class NodeComparator implements Comparator<Node> {
        @Override
        public int compare(Node o1, Node o2) {
            return o1.x - o2.x;
        }
    }


}
